xen: credit2: rework load tracking logic
The existing load tracking code was hard to understad and
maintain, and not entirely consistent. This is due to a
number of reasons:
- code and comments were not in perfect sync, making it
difficult to figure out what the intent of a particular
choice was (e.g., the choice of 18 for load_window_shift);
- the math, although effective, was not entirely consistent.
In fact, we were doing (if W is the lenght of the window):
avgload = (delta*load*W + (W - delta)*avgload)/W
avgload = avgload + delta*load - delta*avgload/W
which does not match any known variant of 'smoothing
moving average'. In fact, it should have been:
avgload = avgload + delta*load/W - delta*avgload/W
(for details on why, see the doc comments inside this
patch.). Furthermore, with
avgload ~= avgload + W*load - avgload
avgload ~= W*load
The reason why the formula above sort of worked was because
the number of bits used for the fractional parts of the
values used in fixed point math and the number of bits used
for the lenght of the window were the same (load_window_shift
was being used for both).
This may look handy, but it introduced a (not especially well
documented) dependency between the lenght of the window and
the precision of the calculations, which really should be
two independent things. Especially if treating them as such
(like it is done in this patch) does not lead to more
complex maths (same number of multiplications and shifts, and
there is still room for some optimization).
Therefore, in this patch, we:
- split length of the window and precision (and, since there
is already a command line parameter for length of window,
introduce one for precision too),
- align the math with one proper incarnation of exponential
smoothing (at no added cost),
- add comments, about the details of the algorithm and the
math used.
While there fix a couple of style issues as well (pointless
initialization, long lines, comments).
Signed-off-by: Dario Faggioli <dario.faggioli@citrix.com>
Reviewed-by: George Dunlap <george.dunlap@citrix.com>